package com.algorithm.ch2.cjm.dynamic;

import java.util.Arrays;

/**
 * Created by jieming.chen on 2020/7/7
 */
public class LengthOfLIS {

    public static void main(String[] args) {
        LengthOfLIS ofLIS = new LengthOfLIS();

        int[] nums = {1,3,6,7,9,4,10,5,6};
        int[] fn = new int[8];

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        fn[0] = 1;  max = 10;
        fn[1] = 1;  max = 9;
        fn[2] = 1;  max = 2;
        fn[3] = 2;  max = 5;
        fn[4] = 2 ; max = 3;
        fn[5] = 3; max = 7;
        fn[6] = 4; max = 101;
        fn[7] = 4;

        int i = ofLIS.lengthOfLIS(nums);
        System.out.println(i);
    }

    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        // 存放每步最长连续子序列
        int[] fn = new int[length];
        // 每步的最大值
        int[] sn = new int[length];
        fn[0] = 1;
        sn[0] = nums[0];
        int res = fn[0];
        for (int i = 1; i < length; i++) {
            int temp = 1;
            int tempMax = nums[i];
            for (int j = 0; j < i; j++) {
                if (nums[i] > sn[j]) {
                    tempMax = nums[i];
                    temp = Math.max(temp, fn[j] + 1);
                }
            }
            fn[i] = temp;
            sn[i] = tempMax;
            res = Math.max(res, fn[i]);
        }
        System.out.println(Arrays.toString(fn));
        System.out.println(Arrays.toString(sn));
        return res;
    }
}
